package 剑指offer;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class 手机屏幕解锁模式 {
    /**
     * 现有一个 3x3 规格的 Android 智能手机锁屏程序和两个正整数 m 和 n ，
     * 请计算出使用最少m 个键和最多 n个键可以解锁该屏幕的所有有效模式总数。
     * 其中有效模式是指：
     * 1、每个模式必须连接至少m个键和最多n个键；
     * 2、所有的键都必须是不同的；
     * 3、如果在模式中连接两个连续键的行通过任何其他键，则其他键必须在模式中选择，不允许跳过非选择键（如图）；
     * 4、顺序相关，单键有效（这里可能跟部分手机不同）。
     * <p>
     * 输入：m,n
     * 代表允许解锁的最少m个键和最多n个键
     * 输出：
     * 满足m和n个键数的所有有效模式的总数
     */

    public static void main(String[] args) {
        System.out.println(solution(1, 9));
    }


    static class Node {
        int x;
        int y;
        int data;

        public Node(int x, int y, int data) {
            this.x = x;
            this.y = y;
            this.data = data;
        }

        public int getX() {
            return x;
        }

        public void setX(int x) {
            this.x = x;
        }

        public int getY() {
            return y;
        }

        public void setY(int y) {
            this.y = y;
        }

        public int getData() {
            return data;
        }

        public void setData(int data) {
            this.data = data;
        }
    }

    static List<Node> nodes = new ArrayList<>();
    static List<Node> nodesB = new ArrayList<>();
    static int[][] arr = new int[3][3];
    static int num = 0;
    static List<Node> path = new ArrayList<>();
    static List<Node> coins = new ArrayList<>();


    public static int solution(int m, int n) {
        // write code here
        if (n <= 0) {
            return 0;
        }
        init(3, 3);
        solutionL(m, n);
        return num;
    }

    public static void init(int m, int n) {
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                count++;
                arr[i][j] = count;
                nodes.add(new Node(i, j, count));
                nodesB.add(new Node(i, j, count));

            }
        }
    }

    private static void solutionL(int m, int n) {
        if (path.size() >= m && path.size() <= n && isExistM(path, coins)) {
            if (path.size() != 0) {
                printNode(path);
                num++;
            }

        }
        if (path.size() > n) {
            return;
        }
        for (int i = 0; i < nodes.size(); i++) {
            Node node = nodes.remove(0);
            Node midNode = null;
            if (path.size() != 0) {
                Node preNode = path.get(path.size() - 1);
                midNode = isCoinM(preNode, node);
                if (midNode != null) {
                    coins.add(midNode);
                }
            }
            path.add(node);
            solutionL(m, n);
            if (midNode != null) {
                coins.remove(midNode);
            }
            path.remove(node);
            nodes.add(node);


        }

    }

    public static int remove(List<Node> nodes, Node node) {
        int i = -1;
        Iterator<Node> iterator = nodes.iterator();
        while (iterator.hasNext()) {
            i++;
            Node next = iterator.next();
            if (next.data == node.data) {
                iterator.remove();
                return i;
            }


        }
        return -1;
    }

    public static Node isCoinM(Node node1, Node node2) {
        int i = node1.getX();
        int j = node1.getY();

        int o = node2.getX();
        int p = node2.getY();

        if ((i + o) % 2 == 0 && (j + p) % 2 == 0) {
            return nodesB.get(arr[(i + o) / 2][(j + p) / 2] - 1);
        }
        return null;
    }

    public static boolean isExistM(List<Node> path, List<Node> coins) {
        boolean flag = true;
        List<Node> g = path;
        Node preNode = null;

        for (Node coin : coins) {
            if (flag) {
                for (int i = 0; i < path.size(); i++) {
                    flag = false;
                    if (coin.data == path.get(i).data) {
                        flag = true;
                        break;
                    }
                }
            }

        }
        for (int i = 0; i < g.size(); i++) {
            Node node = g.get(i);
            if (preNode != null) {
                Node coinM = isCoinM(preNode, node);
                if (coinM != null && i + 1 < g.size()) {
                    if (equal(coinM, g.get(i + 1))) {
                        flag = false;
                    }
                }
                if (i + 1 < g.size()) {
                    coinM = isCoinM(node, g.get(i + 1));
                    if (coinM != null) {
                        if (equal(coinM, preNode)) {
                            flag = false;

                        }
                    }
                }

            }
            preNode = node;
        }
        return flag;
    }

    public static boolean equal(Node node1, Node node2) {
        return node1.data == node2.data ? true : false;
    }

    private static void printNode(List<Node> list) {
        StringBuilder sb = new StringBuilder();
        for (Node node : list) {
            sb.append(node.getData() + "→");
        }
        System.out.println(sb.substring(0, sb.length() - 1));
    }

    public boolean isCoin(int i, int j, int o, int p) {
        if ((i + o) % 2 == 0 && (j + p) % 2 == 0) {
            return true;
        }
        return false;
    }

    /**
     * 实现方案
     *
     * @param m int整型 最少m个键
     * @param n int整型 最多n个键
     * @return int整型
     */
    public static int solutionP(int m, int n) {
        // write code here
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 9;
        }
        int[][] arr = new int[3][3];
        int count = 1;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                arr[i][j] = count++;
            }
        }
        int total = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                int pre = arr[i][j];
                for (int o = 0; o < arr.length; o++) {
                    for (int p = 0; p < arr[0].length; p++) {
                        if (!(i == o && j == p) && !isCoincidence(i, j, o, p)) {
                            System.out.println(pre + "*" + arr[o][p]);
                            total++;
                        }
                    }
                }
            }
        }
        System.out.println(total);
        return total + 9;
    }

    public static boolean isCoincidence(int i, int j, int o, int p) {
        int dis = (int) (Math.pow(i - o, 2) + Math.pow(j - p, 2));

        if (dis == 8 || dis == 4) {
            return true;
        }
        return false;
    }
}
